function gcd(a: number, b: number): number {
  if (Number.isNaN(a) || Number.isNaN(b))
    throw new Error('gcd: NaN');
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}


export class Q {
  public readonly z: number;
  public readonly m: number;
  public static O = new Q(0, 1);
  public static I = new Q(1, 1);
  constructor(z: number, m: number) {
    const g = gcd(z, m) * (m < 0 ? -1 : 1);
    this.z = (z / g) | 0;
    this.m = (m / g) | 0;
  }
  mul(o: Q): Q {
    return new Q(
      this.z * o.z,
      this.m * o.m);
  }
  add(o: Q): Q {
    return new Q(
      this.z * o.m + this.m * o.z,
      this.m * o.m);
  }
  neg(): Q {
    return new Q(
      -this.z,
      this.m);
  }
  sub(o: Q): Q {
    return this.add(o.neg());
  }
  div(o: Q): Q {
    if (o.z === 0)
      throw new Error('div by zero');
    return new Q(
      this.z * o.m,
      this.m * o.z);
  }

  eq(o: Q) { return this.z * o.m === this.m * o.z; }
  eqO() { return this.z === 0; }
  eqI() { return this.z === this.m; }

  gt(o: Q) {
    if (this.eq(o))
      return false;
    else
      return (this.z * o.m > this.m * o.z)
        !== (this.m < 0)
        !== (o.m < 0)
  }
  lt(o: Q) { return o.gt(this); }
  ge(o: Q) { return !o.lt(this); }
  le(o: Q) { return !o.ge(this); }

  toString() {
    if (this.m === 1)
      return `${this.z}`;
    else
      return `${this.z}/${this.m}`;
  }
  static fromString(s: string): Q {
    const [a, b] = s.trim().split('/');
    const pa = Number.parseInt(a);
    const pb = b === undefined ? 1 : Number.parseInt(b);
    return new Q(pa, pb);
  }
}

export function Qs_fromString(s: string): Q[] {
  return s
    .trim()
    .split(' ')
    // .split(/\s*[,\s]\s*/)
    .map(Q.fromString);
}

export class Poly {
  public readonly len: number;
  public readonly coe: Q[];
  constructor(coe: Q[]) {
    let n = coe.length;
    while (n >= 1 && coe[n - 1].eqO())
      --n;

    this.coe = coe.slice(0, n);
    this.len = n;
  }
  add(o: Poly): Poly {
    const len1 = this.len;
    const len2 = o.len;
    const len = Math.max(len1, len2);
    const coe: Q[] = [];

    for (let i = 0; i < len; i++) {
      const q1 = i < len1 ? this.coe[i] : Q.O;
      const q2 = i < len2 ? o.coe[i] : Q.O;
      coe.push(q1.add(q2));
    }

    return new Poly(coe);
  }
  mul(o: Poly): Poly {
    const len1 = this.len;
    const len2 = o.len;
    const len = len1 + len2 - 1;
    const coe: Q[] = [];

    for (let i = 0; i < len; i++) {
      let sum = Q.O;
      for (let j = 0; j <= i; j++) {
        const k = i - j;
        const q1 = j < len1 ? this.coe[j] : Q.O;
        const q2 = k < len2 ? o.coe[k] : Q.O;
        sum = sum.add(q1.mul(q2));
      }
      coe.push(sum);
    }

    return new Poly(coe);
  }
}

export class Mat {
  public readonly d: Q[][];
  public readonly r: number;
  public readonly c: number;

  constructor(d: Q[][]) {
    if (d.length === 0)
      throw new Error('Empty Matrix');
    const l0 = d[0].length;
    for (let i = 1; i < d.length; ++i)
      if (d[i].length !== l0)
        throw new Error(`row ${i + 1} length != row ${1} length`);

    this.d = d;
    this.r = d.length;
    this.c = d[0].length;
  }

  static from(r: number, c: number, f: (i: number, j: number) => Q): Mat {
    if (r <= 0)
      throw new Error('Mat.from');
    const d: Q[][] = [];
    for (let i = 0; i < r; ++i) {
      d[i] = [];
      for (let j = 0; j < c; ++j)
        d[i][j] = f(i, j);
    }
    return new Mat(d);
  }

  static fromS(n: number, f: (i: number, j: number) => Q): Mat {
    if (n <= 0)
      throw new Error('Mat.fromS');
    const d: Q[][] = [];
    for (let i = 0; i < n; ++i) {
      d[i] = [];
      for (let j = 0; j < n; ++j)
        d[i][j] = f(i, j);
    }
    return new Mat(d);
  }

  static O(n: number) { return Mat.fromS(n, () => Q.O); }

  static I(n: number) { return Mat.fromS(n, (i, j) => i === j ? Q.I : Q.O); }

  T(): Mat { return Mat.from(this.c, this.r, (i, j) => this.d[j][i]); }

  mul(o: Mat): Mat {
    if (this.c !== o.r)
      throw new Error('Mat.mul');
    const n = this.c;
    return Mat.fromS(n, (i, j) => {
      let sum = Q.O;
      for (let k = 0; k < n; k++) {
        sum = sum.add(this.d[i][k].mul(o.d[k][j]));
      }
      return sum;
    });
  }

  toLU(): { L: Mat; U: Mat } {
    if (this.r !== this.c) {
      throw new Error('LU decomposition requires a square matrix');
    }
    const n = this.r;
    const L = Mat.I(n);
    const U = Mat.O(n);

    for (let j = 0; j < n; j++) {
      U.d[0][j] = this.d[0][j];
    }

    for (let i = 1; i < n; i++) {
      L.d[i][0] = this.d[i][0].div(U.d[0][0]);
    }

    for (let i = 1; i < n; i++) {
      for (let j = 1; j < n; j++) {
        let sum = Q.O;
        for (let k = 0; k < i; k++)
          sum = sum.add(L.d[i][k].mul(U.d[k][j]));
        U.d[i][j] = this.d[i][j].sub(sum);
      }
      for (let j = i + 1; j < n; j++) {
        let sum = Q.O;
        for (let k = 0; k < i; k++) {
          sum = sum.add(L.d[j][k].mul(U.d[k][i]));
        }
        L.d[j][i] = this.d[j][i].sub(sum).div(U.d[i][i]);
      }
    }

    return { L, U };
  }

  static solve(A: Mat, b: Q[]): { L: Mat; U: Mat; x: Q[]; y: Q[] } {
    if (A.r !== A.c || A.r !== b.length) {
      throw new Error('Invalid matrix dimensions for solving');
    }

    const { L, U } = A.toLU();
    const n = A.r;

    const y: Q[] = [];
    y[0] = b[0].div(L.d[0][0]);
    for (let i = 1; i < n; i++) {
      let sum = Q.O;
      for (let j = 0; j < i; j++) {
        sum = sum.add(L.d[i][j].mul(y[j]));
      }
      y[i] = b[i].sub(sum).div(L.d[i][i]);
    }

    const x: Q[] = [];
    x[n - 1] = y[n - 1].div(U.d[n - 1][n - 1]);
    for (let i = n - 2; i >= 0; i--) {
      let sum = Q.O;
      for (let j = i + 1; j < n; j++) {
        sum = sum.add(U.d[i][j].mul(x[j]));
      }
      x[i] = y[i].sub(sum).div(U.d[i][i]);
    }

    return { L, U, x, y };
  }
  toString(): string {
    return this.d
      .map(line => line
        .map(x => x.toString())
        .join(' '))
      .join('\n');
  }
  static fromString(s: string): Mat {
    console.log(s);
    return new Mat(s
      .trim()
      .split('\n')
      .map(Qs_fromString));
  }
}
